package formal.tree.recursion;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 对称二叉树
 *
 * @author DengYuan2
 * @create 2021-01-14 20:57
 */
public class E_101 {
    public static void main(String[] args) {
        Integer[] a = {1, 2, 2, 3, 4, 4, 3};
        TreeNode t1 = TreeNode.generateTree(a);
        boolean res = isSymmetric(t1);
        System.out.println(res);
    }


    /**
     * 大神-递归
     *
     * @param root
     * @return
     */
    public static boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return helper(root.left, root.right);
    }


    public static boolean helper(TreeNode n1, TreeNode n2) {
        if (n1 == null && n2 == null) {
            return true;
        }
        if (n1 == null || n2 == null) {
            return false;
        }
        if (n1.val != n2.val) {
            return false;
        }
        return helper(n1.left, n2.right) && helper(n1.right, n2.left);
    }

    /**
     * 官方-迭代-队列中两相邻节点一样（t1的左/右节点和t2的右/左节点）：将两个结点的左右子结点按相反的顺序插入队列中
     * 下面被注释掉的是按照思想自己写的，不太好。学到的：--->空的也可以入栈啊！！
     *
     * @param root
     * @return
     */
    public static boolean isSymmetric2(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        //保证对称树的相邻两个节点一致
        queue.offer(root);
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();
//            if (t1.val != t2.val) {
//                return false;
//            }
//            if (t1.left != null && t2.right != null) {
//                queue.offer(t1.left);
//                queue.offer(t2.right);
//            }else if (!(t1.left==null&&t2.right==null)){
//                return false;
//            }
//            if (t2.left != null && t1.right != null) {
//                queue.offer(t2.left);
//                queue.offer(t1.right);
//            }else if (!(t2.left==null&&t1.right==null)){
//                return false;
//            }
//        }
            if (t1 == null && t2 == null) {
                continue;
            }
            if (t1 == null || t2 == null || t1.val != t2.val) {
                return false;
            }
            queue.offer(t1.left);
            queue.offer(t2.right);
            queue.offer(t1.right);
            queue.offer(t2.left);

        }
        return true;

    }
}